package LeetCodeHot100TopInterview;

//自实现队列
class MyQueue {
    Node head;
    Node tail;
    int size ;

    public MyQueue() {
        head = null;
        tail = null;
        size = 0;
    }

    //Put
    public void put(Node node){
        if (this.size == 0){
            head = node;
            tail = node;
        }else {
            //node 在 queue 中由 next 相连
            tail.next = node;
            tail = node;
        }
        size++;
    }

    //Pop
    public Node pop(){
        if (size == 0){
            return null;
        }
        Node ans = head;
        head = head.next;
        ans.next = null;
        size--;
        return ans;
    }
}

public class Q116_PerfectTree {



    //完美二叉树
    //填充它的每个 next 指针，让这个指针指向其下一个右侧节点。
    //如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

    //用层序遍历能做 但是题目要求常数额外空间
    //使用系统 List 与自己实现的区别为 系统的支持了泛型 多包了一层 Node 这个 Node 是额外空间
    public Node connect(Node root) {
        if (root == null){
            return null;
        }
        Node ans = root;
        MyQueue queue = new MyQueue();
        queue.put(root);

        while (queue.size != 0){


            int size = queue.size;
            //上一个弹出的节点
            Node pre = null;
            //整个 for 就是一层
            for (int i = 0; i < size; i++) {
                Node pop = queue.pop();

                if (pop.left != null){
                    queue.put(pop.left);
                }
                if (pop.right != null){
                    queue.put(pop.right);
                }

                if (pre != null){
                    pre.next = pop;
                }
                pre = pop;
            }
        }
        return ans;
    }
}
